/*
 * 	FIFO manager
 *
 * 	based on double-linked list
 *
 * 	$Id: queue.c 11 2008-12-11 03:00:10Z ybc2084 $
 *
 */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <pthread.h>
#include "queue.h"

/*
 * upper bound of quueue length, reserved
 */
const int MAX_LEN_OF_QUEUE = 64;


/********************************
 * queue node method
 ********************************/
static void	QNodeInit(QueueNode *node)
{
	node->data	= NULL;
	node->prev	= NULL;
	node->next	= NULL;
}

static void QNodeFini(QueueNode *node)
{
	/*
	 * XXX: should never destroy node->data here
	 */
	node->prev	= NULL;
	node->next	= NULL;
}

/*
 * two placeholder: lock() and unlock()
 */
static void QNodeLock(const QueueNode *node)
{
}

static void QNodeUnlock(const QueueNode *node)
{
}

/*
 * RETURNS:
 * 		ptr to prev node of 'node' when success;
 * 		NULL otherwise.
 */
static QueueNode* QNodeGetPrevNode(const QueueNode *node)
{
	if (!node)
		return (NULL);

	return (node->prev);
}

/*
 * delete previous node of 'node'
 * RETURNS:
 * 		ptr to deleted previous node if success, NULL otherwise.
 */
static QueueNode* QNodeDelPrevNode(QueueNode *node)
{
	QueueNode	*pnode = NULL;
	QueueNode	*ppnode = NULL;

	if (!node)
		return (NULL);

	/* get prev node and prev-prev node */
	pnode	= node->getPrevNode(node);
	assert(pnode);
	ppnode	= pnode->getPrevNode(pnode);
	assert(ppnode);

	/* relink */
	ppnode->next	= node;
	node->prev		= ppnode;

	/* take off */
	pnode->prev = pnode->next = NULL;

	return (pnode);
}

/*
 * RETURNS:
 * 		prt to newly inserted node if success,
 * 		NULL otherwise.
 */
static QueueNode* QNodeInsPrevNode(QueueNode *node, QueueNode *prev)
{
	if (!node || !prev)
		return (NULL);

	prev->next 		 = node;
	prev->prev 		 = node->prev;
	node->prev->next = prev;
	node->prev 		 = prev;

	return (node->prev);
}

static QueueNode* QNodeGetNextNode(const QueueNode *node)
{
	if (!node)
		return (NULL);

	return (node->next);
}

/*
 * delete next node of 'node'
 * RETURNS:
 * 		ptr to deleted next node if success, NULL otherwise.
 */
static QueueNode* QNodeDelNextNode(QueueNode *node)
{
	QueueNode	*nnode = NULL;
	QueueNode	*nnnode = NULL;

	if (!node)
		return (NULL);

	/* get next node and next-next node */
	nnode	= node->getNextNode(node);
	assert(nnode);
	nnnode	= nnode->getNextNode(nnode);
	assert(nnnode);

	/* relink */
	nnnode->prev	= node;
	node->next		= nnnode;

	/* take off */
	nnode->prev = nnode->next = NULL;

	return (nnode);
}

/*
 * RETURNS:
 * 		ptr to next node of 'node' if success,
 * 		NULL otherwise.
 */
static QueueNode* QNodeInsNextNode(QueueNode *node, QueueNode *next)
{
	if (!node || !next)
		return (NULL);

	next->next 		 = node->next;
	next->prev 		 = node;
	node->next->prev = next;
	node->next 		 = next;

	return (node->next);
}

static QueueNodeData QNodeGetData(const QueueNode *node)
{
	if (!node)
		return (NULL);

	return (node->data);
}

/*
 * RETURNS:
 * 		old data if success, NULL otherwise.
 */
static QueueNodeData QNodeSetData(QueueNode *node, 
		const QueueNodeData const data)
{
	QueueNodeData	oldData = NULL;

	if (!node || !data)
		return (NULL);

	if (node->data)
		oldData = node->data;
	node->data = data;

	return (oldData);
}

/*
 * queue node allocater and deleter
 */
QueueNode* NewQueueNode(void)
{
	QueueNode	*node;

	node = malloc(sizeof(QueueNode));
	if (!node)
		return (NULL);

	memset(node, 0, sizeof(QueueNode));

	node->init			= QNodeInit;
	node->fini			= QNodeFini;

	node->lock			= QNodeLock;
	node->unlock		= QNodeUnlock;
	
	node->getPrevNode	= QNodeGetPrevNode;
	node->delPrevNode	= QNodeDelPrevNode;
	node->insPrevNode	= QNodeInsPrevNode;

	node->getNextNode	= QNodeGetNextNode;
	node->delNextNode	= QNodeDelNextNode;
	node->insNextNode	= QNodeInsNextNode;

	node->getData		= QNodeGetData;
	node->setData		= QNodeSetData;

	/* call constructor */
	node->init(node);

	return (node);
}

void DelQueueNode(QueueNode *node)
{
	node->fini(node);

	free(node);
}

/********************************
 * queue method
 ********************************/
static void QInit(Queue *q)
{
	QueueNode	*head;

	head = NewQueueNode();
	assert(head);

	/* boot strap trick */
	head->prev = head;
	head->next = head;

	/* setting data to null */
	head->setData(head, NULL);

	/* hook on */
	q->setHead(q, head);
}

/*
 * since only two operations - 'pop from front' and 'push to
 * end' - are supported in queue, all nodes remaining in 
 * queue should be released. but this method won't free data
 * pointer contained in queue node, if you need to do that,
 * you'd have to call q->purge(q, true).
 */
static void QFini(Queue *q)
{
	if (!q)
		return;

	/*
	 * do not release data implicitly, you'd have to call 
	 * q->purge(q, true) yourself if you need.
	 */
	q->purge(q, false);

	/* release head node */
	DelQueueNode(q->head);
}

/*
 * RETURNS:
 * 		ptr to head queue node, NULL if failed
 */
static QueueNode* QGetHead(const Queue *q)
{
	if (!q)
		return (NULL);

	return (q->head);
}

/*
 * set head of queue: act as sentinel
 * RETURNS:
 * 		ptr to the newly added head node
 */
static QueueNode* QSetHead(Queue *q, QueueNode * const head)
{
	if (!q || !head)
		return (NULL);

	if (q->head) {
		/* seems make nosense */
		head->data	= q->head->data;
		head->prev	= head;
		head->next	= head;
		free(q->head);
		q->head	= head;
	} else {
		q->head	= head;
	}

	return (q->head);
}

/*
 * dequeue(pop) first node in queue
 * RETURNS:
 * 		ptr to data, NULL if failed
 */
static QueueNodeData QDequeue(Queue *q)
{
	QueueNodeData	 data = NULL;
	QueueNode		*head = NULL;
	QueueNode	   	*nnode = NULL;	/* next node following head */

	if (!q)
		return (data);

	if (q->isEmpty(q))
		return (data);

	head	= q->getHead(q);
	nnode	= head->delNextNode(head);

	assert(nnode);
	data	= nnode->getData(nnode);

	DelQueueNode(nnode);

	return (data);
}

/*
 * enqueue(push) a node to tail of queue
 * RETURNS:
 * 		ptr to newly appended data, NULL if failed
 */
static QueueNodeData QEnqueue(Queue *q, const QueueNodeData data)
{
	QueueNode		*head = NULL;
	QueueNode		*tail = NULL;
	QueueNode		*node = NULL;

	if (!q)
		return (NULL);

	head	= q->getHead(q);
	assert(head);
	tail	= head->getPrevNode(head);
	assert(tail);

	/* alloc new node */
	node	= NewQueueNode();
	assert(node);
	node->setData(node, data);

	tail->insNextNode(tail, node);

	return (data);
}

static bool QIsEmpty(const Queue *q)
{
	const QueueNode	*head;

	if (!q)
		return (false);

	head = q->getHead(q);

	if (head->next == head)
		return (true);
	else
		return (false);
}

/*
 * always return false, since no limit 
 * on queue capacity now
 */
static bool QIsFull(const Queue *q)
{
	return (false);
}

/*
 * purge all entities in queue.
 * 'release' flag whether free qnode->data
 */
static void	QPurge(Queue *q, bool release)
{
	QueueNode		*head = NULL;
	QueueNode		*node = NULL;
	QueueNodeData	 pData;

	if (!q)
		return;

	head = q->getHead(q);
	assert(head);

	/* 
	 * release all nodes, except head, if 'release' flag 
	 * set true, release data contained in queue node.
	 */
	while (! q->isEmpty(q)) {
		node = head->delNextNode(head);
		if (release) {
			pData = node->getData(node);
			free(pData);
		}
		free(node);
	}
}

/*
 * queue allocater and deleter
 */
Queue* NewQueue(void)
{
	Queue	*q;

	q = malloc(sizeof(Queue));
	if (!q)
		return (NULL);

	memset(q, 0, sizeof(Queue));

	q->init		= QInit;
	q->fini		= QFini;

	q->getHead	= QGetHead;
	q->setHead	= QSetHead;
	
	q->dequeue	= QDequeue;
	q->enqueue	= QEnqueue;

	q->isEmpty	= QIsEmpty;
	q->isFull	= QIsFull;

	q->purge	= QPurge;

	/* call constructor */
	q->init(q);

	return (q);
}

void DelQueue(Queue *q)
{
	q->fini(q);

	free(q);
}

